#define _CRT_SECURE_NO_WARNINGS

//数组排序--归并排序练习

class Solution {
public:
    vector<int> tmp;
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        MergeSort(nums, 0, nums.size()-1);
        return nums;
    }
    void MergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return;
        //1.选择中心点进行划分
        int mid = left + (right - left)/2;
        //[left, mid] [mid + 1, right]
        //2.对子区间进行处理
        MergeSort(nums, left, mid);
        MergeSort(nums, mid + 1, right);
        //3.合并两个有序子区间
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        //4.还原
        for(i = left; i <= right; i++)
            nums[i] = tmp[i - left]; 
    }
};